class Solution:
    def nthUglyNumber(self, n: int) -> int:
        s = [0,1]
        if n == 1:
            return 1
        i, j, k = 1, 1, 1
        t2, t3, t5 = 2, 3, 5
        while True:
            m = min(t2,t3,t5)
            s.append(m)
            while 2*s[i]<=m:
                i += 1
            t2 = 2*s[i]
            while 3*s[j]<=m:
                j += 1
            t3 = 3*s[j]
            while 5*s[k]<=m:
                k += 1
            t5 = 5*s[k]
            if len(s) == n+1:
                return m

if __name__ == '__main__':
    c = Solution()
    print(c.nthUglyNumber(10))